#include <iostream>
#include <cstdio>
#include <stack>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

class Solution {
private:
    vector<int> min_heap;
    vector<int> max_heap;
public:
    void Insert(int num)
    {
        int size=min_heap.size()+max_heap.size();
        if(size%2==0){
            //偶数个，则把他加入到小顶堆(较大的部分),加入之前需调整大顶堆(较小的部分)
            if(max_heap.size()>0 && max_heap[0]>num){
                //在加入小顶堆之前，调整大顶堆
                max_heap.push_back(num);
                push_heap(max_heap.begin(),max_heap.end(),less<int>());
                num=max_heap[0];
                pop_heap(max_heap.begin(),max_heap.end(),less<int>());
                max_heap.pop_back();
            }
            min_heap.push_back(num);
            push_heap(min_heap.begin(),min_heap.end(),greater<int>());
        }else{
            //奇数个，加入到大顶堆(较小的部分)
            //同时需要调整小顶堆(较大的部分)
            if(min_heap.size()>0 && min_heap[0]<num){
                min_heap.push_back(num);
                push_heap(min_heap.begin(),min_heap.end(),greater<int>());
                num=min_heap[0];
                pop_heap(min_heap.begin(),min_heap.end(),greater<int>());
                min_heap.pop_back();
            }
            max_heap.push_back(num);
            push_heap(max_heap.begin(),max_heap.end(),less<int>());
        }
    }

    double GetMedian()
    { 
        int size=min_heap.size()+max_heap.size();
        if(size%2==0){
            return (min_heap[0]+max_heap[0])/2.0;
        }else{
            return min_heap[0];
        }
    }
};

int main(){
    Solution s;
    s.Insert(1);
    cout << s.GetMedian()<<endl;
    s.Insert(2);
      cout << s.GetMedian()<<endl;
    s.Insert(3);
      cout << s.GetMedian()<<endl;
    s.Insert(4);
      cout << s.GetMedian()<<endl;
    s.Insert(5);


    return 0;
}